#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

struct HuffmanCode
{
    char ch;
    size_t freq;
    HuffmanCode* left;
    HuffmanCode* right;
    HuffmanCode(char ch,size_t freq)
    {
        this->ch=ch;
        this->freq=freq;
        left=right=nullptr;
    }
};
struct Com
{
    bool operator()(HuffmanCode*a,HuffmanCode*b)
    {
        return a->freq>b->freq;
    }
};
HuffmanCode* buildHuffmanCode(map<char,size_t>& freq,size_t& EncodeLength)
{
    priority_queue<HuffmanCode*, vector<HuffmanCode*>,Com> q;
    for(auto &freqs:freq)
    {
        q.push(new HuffmanCode(freqs.first,freqs.second));
    }

    while(q.size()>1)
    {
        HuffmanCode* hf1=q.top();
        q.pop();
        HuffmanCode* hf2=q.top();
        q.pop();
        EncodeLength+=hf1->freq+hf2->freq;
        //用#代替每次新生成的节点
        HuffmanCode * newnode = new HuffmanCode('#',hf1->freq+hf2->freq);
        newnode->left=hf1;
        newnode->right=hf2;
        q.push(newnode);
    }
    return q.top();
}
void Encode(HuffmanCode*& root,const string& code,map<char,string>& freq1)
{
    if(!root)return;
    if(!root->left&&!root->right)
    {
        freq1[root->ch]=code;
    }
    Encode(root->left,code+"0",freq1);
    Encode(root->right,code+"1",freq1);
}
int main()
{
    int num;
    cin>>num;
    map<char,size_t> freq;
    
    for(int i=0;i<num;i++)
    {
        int fr=0;
        char ch;
        cin>>ch>>fr;
        freq[ch]=fr;
    }
    size_t EncodeLength=0;
    HuffmanCode* root=buildHuffmanCode(freq,EncodeLength);

    //计算压缩这段字符需要的最短字符串长度
    cout<<"压缩所有字符的二进制序列的最短长度"<<EncodeLength<<endl;

    map<char,string> freq1;
    Encode(root,"",freq1);

    cout<<"每个字符压缩后的二进制序列"<<endl;
    for(auto &m:freq1)
    {
        cout<<m.first<<" "<<m.second<<endl;
    }
    return 0;
}

